package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。 
//
// 设计一个算法使得这 m 个子数组各自和的最大值最小。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [7,2,5,10,8], m = 2
//输出：18
//解释：
//一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
//因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,4,5], m = 2
//输出：9
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,4,4], m = 3
//输出：4
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 106 
// 1 <= m <= min(50, nums.length) 
// 
// Related Topics 二分查找 动态规划 
// 👍 459 👎 0



public class SplitArrayLargestSum{
    public static void main(String[] args) {
        Solution solution = new SplitArrayLargestSum().new Solution();
        System.out.println(solution.splitArray(new int[]{1,2,3,4,5}, 2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int splitArray(int[] nums, int m) {
            if (nums == null || nums.length == 0 || nums.length < m) {
                return -1;
            }

            long l = -1; // max(nums[i])
            long r = 0;  // sum(nums[i])
            for (int num : nums) {
                l = Math.max(num, l);
                r = r + num;
            }

            int group = 0;
            long mid = 0;
            while (l + 1 < r) {
                mid = (r - l) / 2 + l;
                group = check(nums, mid);
                if (group > m) {
                    l = mid;
                } else {
                    r = mid;
                }
            }

            if (check(nums, l) <= m) return (int) l;
            return (int) r;
        }

        private int check(int[] nums, long block) {
            long sum = 0;
            int group = 1;
            for (int i : nums) {
                /*if (sum >= block) {
                    group += 1;
                    sum = i;
                } else {
                    sum += i;
                }*/
                if(sum + i <= block){
                    sum += i;
                }else{
                    group += 1;
                    sum = i;
                }
            }
            return group;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
